Documents can be described by internal computer structures in accordance with varying computer languages. For example, a document represented by one computer may use the Word Perfect language while a document represented by a different computer may use the Microsoft Word language. In order to make document processing more efficient, it is often desirable to enable interchange between documents represented using different languages. Thus, there should be consistency between interrelated documents.
In order to provide such consistency enabling interchange of documents, the Standard Generalized Markup Language (SGML) for example, was developed as an external representation making document interchange possible.
There are many editing applications wherein objects to be edited have hierarchical structures. Thus, any editing step must conform to a formal specification of possible content. The editing of documents described in SGML document type definitions is a specific instance of structured document editing.
Structured document editing has been deemed by many users as an excessively restrictive way of constructing structured objects (e.g., programs or documents) because of the strong ordering constraints (i.e., top-bottom, and sometimes left-right, as well) that grammar-based editors typically impose. Thus, a more relaxed version of syntax-directed editing is desirable. Often the class of hierarchical structures of interest can be made to correspond to incomplete parse trees of a particular context-free grammar (set of rules), i.e., any tree remaining after having deleted zero or more proper subtrees of a parse tree of the same grammar.
For example, given the following grammar, it would be desirable to easily and efficiently determine whether a user could freely build a hierarchical structure;
Doc.fwdarw.(Front, Body, Back) PA1 Body.fwdarw.(Intro, Mn. Sections.sup.+, App..sup.+)
A parse tree corresponding to the above grammar is illustrated in FIG. 1.
An SGML document class is defined by a document type definition or DTD (context-free grammar). In accordance with SGML, a document is classified as weakly valid if it can be made valid solely by the insertion of additional structural mark-up in appropriate places. For example, if "Front" was missing from the parse tree of FIG. 1 as shown in FIG. 2, the document would be classified as weakly valid since the simple insertion of "Front" would validate the parse tree. Similarly, if "Body" was missing from the parse tree of FIG. 1 as in FIG. 3, the document would also be classified as weakly valid since the insertion of begin and end tags around the [Intro, Sections.sup.+, Appendix] would result in a valid parse tree. A document is valid if and only if the structure is a member of language defined by the DTD.
Thus, if, for example, a user wanted to add a node "x" beneath node "Body", it would be highly desirable to enable one to easily check for validity of this action, thus determining whether the action is legalized if some action can be taken. It is further desirable to perform such a check in an arbitrary, convenient order to enable the user to freely work on document segments.